public class Solution {
    //买卖股票|||
    public int maxProfit(int[] prices) {
        int n = prices.length;
        int[][] f = new int[n][3];
        int[][] g = new int[n][3];
        f[0][0] = -prices[0];
        f[0][1] = -0X3f3f3f3f;
        f[0][2] = -0X3f3f3f3f;
        g[0][0] = 0;
        g[0][1] = -0X3f3f3f3f;
        g[0][2] = -0X3f3f3f3f;
        for (int i = 1; i < n; i++) {
            for (int j = 0; j < 3; j++) {
                f[i][j] = Math.max(f[i - 1][j], g[i - 1][j] - prices[i]);
                g[i][j] = g[i - 1][j];
                if (j - 1 >= 0) g[i][j] = Math.max(f[i - 1][j - 1] + prices[i], g[i - 1][j]);
            }
        }
        int max = 0;
        for (int i = 0; i < 3; i++) {
            if (max < g[n - 1][i]) {
                max = g[n - 1][i];
            }
        }
        return max;
    }
    //买卖股票IV
    public int maxProfit(int k, int[] prices) {
        int INF = 0X3f3f3f3f;
        int n = prices.length;
        if(k > n) {
            k = n/2;
        }
        int[][] f = new int[n][k+1];
        int[][] g = new int[n][k+1];
        for(int i = 1; i < k+1; i++) f[0][i] = g[0][i] = -INF;
        f[0][0] = -prices[0];
        g[0][0] = 0;
        for(int i = 1; i< n; i++) {
            for(int j = 0; j < k+1; j++) {
                f[i][j] = Math.max(f[i-1][j],g[i-1][j] - prices[i]);
                g[i][j] = g[i-1][j];
                if(j-1>=0) g[i][j] = Math.max(f[i-1][j-1] + prices[i],g[i-1][j]);
            }
        }
        int max = 0;
        for(int i = 0; i <= k; i++) {
            if(max < g[n-1][i]) {
                max = g[n-1][i];
            }
        }
        return max;
    }
    //最大子数组和
    public int maxSubArray(int[] nums) {
        int n = nums.length;
        int[] dp = new int[n];
        dp[0] = nums[0];
        for(int i = 1; i < n;i++) {
            dp[i] = Math.max(nums[i],dp[i-1]+nums[i]);
        }
        int max = -Integer.MAX_VALUE;
        for(int i = 0; i < n; i++) {
            if(max < dp[i]) {
                max = dp[i];
            }
        }
        return max;
    }
    //环形子数组最大和
    public int maxSubarraySumCircular(int[] nums) {
        int n = nums.length;
        //f数组装入某个位置的最大子序列和
        int[] f = new int[n];
        //g数组装入某个位置最小子序列和
        int[] g = new int[n];
        f[0] = nums[0];
        g[0] = nums[0];
        int sum = 0;
        for(int i = 0; i < n; i++) {
            sum+=nums[i];
        }
        for(int i = 1; i < n; i++) {
            f[i] = Math.max(nums[i],f[i-1]+nums[i]);
            g[i] = Math.min(nums[i],g[i-1]+nums[i]);
        }
        int gmin = Integer.MAX_VALUE;
        for(int i = 0; i < n; i++) {
            if(g[i] < gmin) {
                gmin = g[i];
            }
        }

        int fmax = -Integer.MAX_VALUE;
        int gmax = -Integer.MAX_VALUE;
        for(int i = 0; i<n; i++) {
            if(f[i] > fmax) {
                fmax = f[i];
            }
            if(sum-g[i] > gmax) {
                gmax = sum - g[i];
            }
        }
        //全是负数的情况
        if(sum == gmin) {
            return fmax;
        }
        return Math.max(fmax,gmax);
    }
}
